As computers and electronic devices become more ubiquitous, it becomes increasingly important that computer-human interfaces allow easy and efficient communication with these devices. With many people interacting with devices for longer periods of time, improvements in input systems can have significant benefits. For example, considerable research has focused on various types of input systems for personal data assistants (PDAs). One popular PDA input system displays a virtual keyboard 100 on a touch-sensitive display 110, as shown in FIG. 1. By tapping the displayed keys with a stylus 120, a user can input a desired sequence of characters. The particular layout of characters on the virtual keyboard 100 is shown in detail in FIG. 2A. Although this simple ABC layout is attractive because it can be quickly learned by a novice, it is not the most efficient layout for expert users. Since common keys such as space, E, and A, are not centrally located, the user will often need to move the stylus large distances across the keyboard. FIG. 2B shows a slightly improved layout with the space key centrally located. This ABC-center layout is somewhat more efficient, but still far from optimal. The input system design problem for this device is to determine the layout that provides the highest text input speed for expert users. In short, the problem is to find the layout associated with the highest peak expert input rate.
One method for searching for the optimal layout is empirical trail-and-error. As illustrated in FIG. 3, the first step 300 of this approach is to select an input device and input data corpus. The data corpus contains information that is considered representative of data expected to be entered during typical use of the device (e.g., collections of common sentences, phrases, words, and other character sequences). In the next step 310, a particular key layout, or interface map, is selected. The map is a particular assignment of characters to the keys on the virtual keyboard (e.g., the ABC key layout shown in FIG. 2A). Then, in step 320, a group of representative users is trained with the resulting input system until they reach expert level. Their input rates are then empirically measured. These measured rates will depend on the selected keyboard layout. At decision block 330, it is decided whether or not a satisfactory layout has not been found. If not, one returns to step 310 and selects another key layout (e.g., the ABC-center layout shown in FIG. 2B). Another empirical trial is then performed in step 320 to test the new key layout. When the empirical tests are complete, the layout with the highest rate is selected at step 340.
There are several major difficulties with this trial-and-error method. One problem is that it is very expensive and time consuming to perform an empirical trail for every layout tested for the device, training a group of users to expert level each time. It is not practical to test more than a few layouts, and it is impossible to exhaustively test the entire set of more than 1025 layouts. In addition, of the handful of layouts selected for testing, there is no proof that the optimal layout is among them. This approach provides no systematic method for selecting good layouts to test, or for ensuring that the next layout tested will be any better than the last. The trial-and-error method for searching for the optimal layout is more of an art than a science, and it is not likely to effectively optimize the layout for the device. The problem of optimizing the input system thus remains unsolved.
There is a systematic method of searching for an optimal layout while avoiding some of the drawbacks of empirical trial-and-error. Instead of measuring the input speeds of real users trained to expert level, this approach uses an empirically-calibrated theoretical model of human movement to predict the input speeds of model users. Combining these predicted movement speeds with a keyboard layout map and a model of the data corpus, a peak expert input rate for the layout can be calculated. A similar calculation can be performed for various alternative layouts, allowing a large number of different layouts to be tested and compared without additional empirical measurements. As illustrated in FIG. 4, the first step 400 of this method selects an input device and data corpus. In the next step 410, empirical measurements are made of users entering data using the device. These measurements are used in step 420 to calibrate the theoretical model of human movement to the particular device. (For example, Fitts' law of human movement models the time to hit a second key immediately after hitting a first key as a function of the distance between the two keys and the size of the second key. The function has two parameters that are adjusted to fit the model to the empirical measurements made with the input device.) Once the model is calibrated, the empirical data are discarded and are not used further. In the first step of the iterative search, a particular layout is selected in step 430. Then, in step 440, the peak expert input rate is calculated using the calibrated model. For example, combining the key distances with the layout information allows the model to predict the time to enter a second character immediately following a first character. Statistical information about the data corpus (specifically, bi-gram probabilities representing how often one character is followed by another in the data corpus) are then combined with these predictions to calculate a predicted peak expert input rate. At step 450 a decision is made whether or not to select another layout and repeat the calculation. Finally, after calculations have been performed for various layouts, the layout with the highest predicted peak expert input rate is selected in step 460. FIGS. 2C and 2D show examples of two layouts, called OPTI and FITALY, which were found using this technique based on empirically-calibrated theoretical models.
Using a theoretical model to search for optimal layouts allows a computational search to replace expensive and time-consuming empirical trials. However, this theoretical approach has significant problems of its own. For example, Fitts' law is inaccurate for small movements (i.e., one or two key widths). Because a large proportion of movements during input involve such small movements, the predicted input rates will be inaccurate, distorting the optimization process. In addition, Fitts' law is an overly simplistic model of human movement because it assumes that the movement time depends only on the distance between keys, and not on any other factors. Insofar as such factors may significantly correlate with movement time, the predicted input rates will be even more inaccurate since the model fails to take these factors into account. Theoretical models like Fitts' law are also limited to a small class of keyboard-like input devices because they are based on the assumption that input actions are linear movements of a single pointer between selectable elements in a plane. The models cannot be applied to other types of input device actions, such as ten fingers using a conventional keyboard, or intricate hand gestures using a glove interface.
Although the current challenges of input system design have been illustrated above using the example of trying to find an optimal layout of a keyboard for stylus-based input to a PDA, they also apply to many other types of human-computer interface design. For example, similar problems arise when searching for an optimal layout of characters on a conventional keyboard, as well as on other keypads and keyboards commonly used for interfacing with electronic devices such as cellular telephones, pocket personal computers, calculators, microwave ovens, automated teller machines, and airline check-in kiosks, just to name a few.
The problem also applies to the design of input systems that do not involve keyboards with characters. To state the problem more generally, given 1) an input device that translates a set of distinguishable user actions into a set of unique input signals, 2) a set of unique signifiers that a user desires to communicate using the input device, and 3) knowledge of the patterns of signifiers expected to be communicated, the problem is to find an optimized map between the input device signals and the set of distinct signifiers.
Existing input system optimization methods based on theoretical models provide only inaccurate solutions and are limited to a relatively small class of simple user interface devices. Methods based on empirical testing, on the other hand, are very time consuming, expensive, and are based largely on guesswork. Therefore, there is a need for methods to design input systems that overcome the problems of both empirical trail-and-error approaches and approaches based on theoretical models of movement.